#include <lcthw/list_algos.h>
#include <lcthw/dbg.h>

inline void ListNode_swap(ListNode *a, ListNode *b)
{
    void *temp = a->value;
    a->value = b->value;
    b->value = temp;
}

int List_bubble_sort(List *list, List_compare cmp)
{
    int sorted = 1;

    if(List_count(list) <= 1) {
        return 0;  // already sorted
    }
// 多余，冒泡排序每次循环都会从后减少一次比较
    do {
        sorted = 1;
        LIST_FOREACH(list, first, next, cur) {
            if(cur->next) {
                if(cmp(cur->value, cur->next->value) > 0) {
                    ListNode_swap(cur, cur->next);
                    sorted = 0;
                }
            }
        }
    } while(!sorted);

    return 0;
}
// 不拆分，只管把两个合并成一个
inline List *List_merge(List *left, List *right, List_compare cmp)
{
    List *result = List_create();
    void *val = NULL;

    while(List_count(left) > 0 || List_count(right) > 0) {
        if(List_count(left) > 0 && List_count(right) > 0) {
            if(cmp(List_first(left), List_first(right)) <= 0) {
                val = List_shift(left);
            } else {
                val = List_shift(right);
            }

            List_push(result, val);
        } else if(List_count(left) > 0) {
            val = List_shift(left);
            List_push(result, val);
        } else if(List_count(right) > 0) {
            val = List_shift(right);
            List_push(result, val);
        }
    }

    return result;
}
// 拆分
List *List_merge_sort(List *list, List_compare cmp)
{
    if(List_count(list) <= 1) {
        return list;
    }
    int middle = List_count(list) / 2 ;
    // List *left=NULL;
    // List *right=NULL ;

    List *listnew = List_copy(list);
    List *right= List_split(listnew,middle);
    List *left = List_copy(listnew);


// 循环，把表切成两半
    // LIST_FOREACH(list, first, next, cur) {
    //     if(middle > 0) {
    //         List_push(left, cur->value);
    //     } else {
    //         List_push(right, cur->value);
    //     }

    //     middle--;
    // }


// 递归，切分至更小,2个一组
    List *sort_left  = List_merge_sort(left, cmp);
    List *sort_right = List_merge_sort(right, cmp);
// 合并后把原分支销毁，带sort前缀的是已排好的
    if(sort_left != left) List_destroy(left);
    if(sort_right != right) List_destroy(right);

    return List_merge(sort_left, sort_right, cmp);
}


void List_insert_sorted(List *list , void *newvalue, List_compare cmp)
{
    ListNode *node = calloc(1, sizeof(ListNode));
    node->value = newvalue;
    LIST_FOREACH(list, first, next, cur) 
        if (cur->next && cur->prev){
            if((cmp(cur->value,newvalue) <= 0) && (cmp(newvalue,cur->next->value) <= 0))
                {
                    node->prev  = cur;
                    node->next  = cur->next;  
                    cur->next->prev   =   node;
                    cur->next   = node;
                    break;
                }
        }
        else if (cur->next && !cur->prev){
             if(cmp(cur->value,newvalue) > 0 ){
                    cur->prev  = node;
                    node->next = cur;
                    node->prev = NULL;
                    list->first = node;
                    break;
             }
             else if((cmp(cur->value,newvalue) <= 0) && (cmp(newvalue,cur->next->value) <= 0))
                {
                    node->prev  = cur;
                    node->next  = cur->next;  
                    cur->next->prev   =   node;
                    cur->next   = node;
                    break;
                }
        }
        else if (!cur->next && cur->prev){
             if(cmp(cur->value,newvalue) <= 0 ){
                    cur->next  = node;
                    node->prev = cur;
                    node->next = NULL;
                    list->last = node; 
                    break;    
             }
               
        }
    return;

}

